HW#3 --- last modified January 28 2019 19:26:59..

Solution set.

Due date: Apr 4

Files to be submitted:
  Hw3.zip

Purpose: To gain experience with distributed algorithms

Related Course Outcomes:

The main course outcomes covered by this assignment are:

CLO2 -- Analyze or code a parallel algorithm using a thread library

CLO3 -- Analyze or code a parallel algorithm using a library such as OpenCL

CLO4 -- Analyze the correctness and run time of a distributed algorithm

Specification:

This homework will consist of two parts, a written part and a coding part. Both parts will be submitted in the Hw3.zip file. The written part should be in a file Hw3.pdf. For the written part of the homework you should write solutions for the following questions. In what you turn in, make sure to write the names and student ids for each group member. For each problem, first copy and paste the question, then write your solution to it beneath it.

1. Devise a CREW PRAM algorithm that selects the median of `n` input numbers in `O(\log n)` steps using `n/ log n` processors. Assume that the `n` input numbers are initially located in global memory locations `1` through `n`.
2. Give a concrete example with 8 processors where the faulty processor succeeds in foiling a threshold choice in the Byzantine agreement algorithm.
3. Carefully give a DMRC algorithm for determine which node in a communications network has the most incoming traffic. Assume the input consist of (key; value) pairs of the form `((i,j); n_(i,j))` where the key is the pair `(i,j)` and `n_(i,j)` is the number of bytes of traffic from node `i` to `j` in the network.

For the coding part of the assignment I would like to code a parallel algorithm for finding maximal cliques in a graph. Recall a clique is a set of vertices `C` in a graph `G`, such that for every `i, j in C`, the edge `{i,j}` is in `G`. Such a clique is maximal if it is not a proper subset of any other clique. Finding a clique is related to finding independents sets. Given a graph `G = (V, E)`, call `bar{G} = (V, \bar{E})`, where `bar{E} = \{(i,j) | (i,j) in V times V, (i,j) !in E\}`, the dual graph of `G`. A set is a clique in `G` if and only it is as an independent set in `bar{G}`. So I want you to modify parallel MIS from class to compute maximal cliques in parallel. Before you code anything, write up as part of Hw3.pdf, the pseudo code for your modification to ParallelMIS and briefly argue why it will correctly compute maximal cliques. Your program will be tested from the command line as follows:

javac ParallelClique.java
java ParallelClique graph_file

0 1 0 1 0 0
1 0 1 0 0 0
0 1 0 0 1 0
1 0 0 0 1 0
0 0 1 1 0 1
0 0 0 0 1 0

3
5

Each vertex in the clique is listed on its own line from least to greatest. I subtracted 1 off each vertex name I used on the slide, so that indexes can agree with the default of arrays in Java and Python.

Point Breakdown